package fourthweek.Linked;

import fourthweek.ElementNotFoundException;
import fourthweek.ListADT;
import secondweek.EmptyCollectionException;
import secondweek.LinearNode;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;


public class LinkedList<T> implements Iterable<T>, ListADT<T> {

    protected int count;
    protected LinearNode<T> head, tail;
    protected int modCount;
    public LinkedList() {
        count = 0;
        head = tail = null;
        modCount = 0;
    }

    @Override
    public T removeFirst() {
        if (isEmpty())
            throw new EmptyCollectionException("LinkedList");

        LinearNode<T> current = head;// 当前的结点

        /**
         * 是否相等
         */
        if (size() == 1)
            head = tail = null;
        else
            head = current.getNext();//

        count--;
        modCount++;
        return current.getElement();
    }
    @Override
    public T removeLast() {
        if (isEmpty())
            throw new EmptyCollectionException("LinkedList");
        boolean found = false;
        LinearNode<T> previous = null;
        LinearNode<T> current = head;

        while (current != null && !found) {
            if (current.equals(tail)) {
                found = true;
            } else {
                previous = current;
                current = current.getNext();
            }
        }
        if (size() == 1)
            head = tail = null;
        else {
            tail = previous;
            tail.setNext(null);
        }
        count--;
        modCount++;
        return current.getElement();
    }
    @Override
    public T remove(T targetElement) {
        if (isEmpty())
            throw new EmptyCollectionException("LinkedList");

        boolean found = false;
        LinearNode<T> previous = null;
        LinearNode<T> current = head;

        while (current != null && !found)
            if (targetElement.equals(current.getElement()))
                found = true;
            else {
                previous = current;
                current = current.getNext();
            }

        if (!found)
            throw new ElementNotFoundException("LinkedList");

        if (size() == 1)
            head = tail = null;
        else if (current.equals(head))
            head = current.getNext();
        else if (current.equals(tail))
        {
            tail = previous;
            tail.setNext(null);
        } else
            previous.setNext(current.getNext());
        count--;
        modCount++;

        return current.getElement();
    }
    @Override
    public T first() {
        if (isEmpty())
            throw new EmptyCollectionException("queue");
        else
            return head.getElement();
    }
    @Override
    public T last() {
        if (isEmpty())
            throw new EmptyCollectionException("queue");
        else
            return tail.getElement();
    }
    @Override
    public boolean contains(T target) {
        if (isEmpty())
            throw new EmptyCollectionException("LinkedList");
        LinearNode temp = head;
        while((temp.getElement() != target)&&(temp !=  null)){
            temp = temp.getNext();
        }
        return temp.getElement() == target;
    }
    @Override
    public boolean isEmpty() {
        return count == 0;
    }
    @Override
    public int size() {
        return count;
    }
    @Override
    public String toString() {
        LinearNode<T> temp = head;
        String result = "";
        while(temp != null)
        {
            result += temp.getElement().toString() + " ";
            temp = temp.getNext();
        }
        return result;
    }
    @Override
    public Iterator<T> iterator() {
        return new LinkedListIterator();
    }
    private class LinkedListIterator implements Iterator<T> {
        private int iteratorModCount; // the number of elements in the
        private LinearNode<T> current; // the current position

        /**
         * 构造函数
         */
        public LinkedListIterator() {
            current = head;
            iteratorModCount = modCount;
        }

        /**
         * 判定是否还有下一个结点
         */
        public boolean hasNext() throws ConcurrentModificationException {
            if (iteratorModCount != modCount)
                throw new ConcurrentModificationException();

            return (current != null);
        }

        /**
         * 返回元素
         */
        public T next() throws ConcurrentModificationException {
            if (!hasNext())
                throw new NoSuchElementException();

            T result = current.getElement();
            current = current.getNext();
            return result;
        }

        /**
         * 移除元素
         */
        public void remove() throws UnsupportedOperationException {
            throw new UnsupportedOperationException();
        }
    }

}
